Bevor we perform a move is it essential to decide if the following state is a deadlock or not. A deadlock situation in sokoban is the state when a box is not moveable or if it is not possible to move the the box back from a wall. It is only necessary to check the box which moved at last because only the move of this box could produce a deadlock situation.

%When we are in the main function, we have to stop when the board becomes unsolvable. By unsolvable we mean that it exists one box that we can not move anymore even if we move all the other boxes: the box is in a dead lock. Every time we move a box, we look if we can still move all the boxes.
The following rules are used to determinate if a state is a deadlock.

\begin{enum}
	\item a box on a goal is never a deadlock
	\item a box which is next to wall on one dimension must be between two empty squares or other boxes, which are moveable, in the other dimension to be not in a deadlock
	\item two boxes next to each other which next to a wall is a deadlock
	\item a box next to a continous wall with the shape of a "U" and no goal is at the base line of the U-shape is deadlock
	\item four boxes in a square formation is a deadlock  

\end{enum}

The following pictures showing some examples of deadlocks:

If there is one wall above or below and one to the left or to the right
\begin{figure}[htbp]
  \centering
  \fbox{
  	\includegraphics[width=60mm]{deadlock1a.png}
  }
  \caption{Deadlock situation which breaks rule number 2}
  \label{pic:deadlock1a}
\end{figure}
\begin{figure}[htbp]
  \centering
  \fbox{
  	\includegraphics[width=60mm]{deadlock1b.png}
  }
  \caption{Deadlock situation which breaks rule number 2}
  \label{pic:deadlock1b}
\end{figure}

\begin{figure}[htbp]
  \centering
  \fbox{
  	\includegraphics[width=60mm]{deadlock1c.png}
  }
  \caption{Deadlock situation which breaks rule number 2}
  \label{pic:deadlock1c}
\end{figure}

\begin{figure}[htbp]
  \centering
  \fbox{
  	\includegraphics[width=60mm]{deadlock1d.png}
  }
  \caption{Deadlock situation which breaks rule number 2}
  \label{pic:deadlock1d}
\end{figure}


\begin{figure}[htbp]
  \centering
  \fbox{
 	\includegraphics[width=60mm]{deadlock2.png}
  }
  \caption{Deadlock situation which breaks rule number 3}
  \label{pic:deadlock2}
\end{figure}

\begin{figure}[htbp]
  \centering
  \fbox{
	\includegraphics[width=60mm]{deadlock3a.png}
  }
  \caption{Deadlock situation which breaks rule number 4}
  \label{pic:deadlock3a}
\end{figure}

\begin{figure}[htbp]
  \centering
  \fbox{
	\includegraphics[width=60mm]{deadlock3b.png}
  }
  \caption{Deadlock situation which breaks rule number 4}
  \label{pic:deadlock3b}
\end{figure}


\begin{figure}[htbp]
  \centering
  \fbox{
	\includegraphics[width=60mm]{deadlock4.png}
  }
  \caption{Deadlock situation which breaks rule number 5}
  \label{pic:deadlock4}
\end{figure}


  